package isFlipedString;

public class Solution {
    public boolean isFlipedString(String s1, String s2) {
        //
//        if(s1.length()!=s2.length()) return false;
//        int n = s1.length();
//        for (int i = 0; i < n; i++) {
////            System.out.println(s1.substring(0,i+1));
////            System.out.println(s2.substring(n-i-1,n));
////            System.out.println();
//            if(s1.substring(0,i+1).equals(s2.substring(n-i-1,n)) && s1.substring(i+1,n).equals(s2.substring(0,n-i-1))) {
//                return true;
//            }
//        }
//        return false;
        return s1.length() == s2.length() && contain(s1+s1,s2);
    }
    // KMP算法
    private boolean contain(String s1,String s2) {
        int[] next = getNext(s2);
        int n = s1.length();
        for (int i = 1,j = 0; i < n; i++) {
            while (j>0&&s1.charAt(i) != s2.charAt(j)) {
                j = next[j-1];
            }
            if(s1.charAt(i) == s2.charAt(j)) {
                j++;
            }
            if(j == s2.length()) {
                return true;
            }
        }
        return false;
    }
    private int[] getNext(String s) {
        int[] next = new int[s.length()];
        for (int i = 1,j=0; i < s.length(); i++) {
            while(j>0&&s.charAt(j) != s.charAt(i)) {
                j = next[j-1];
            }
            if(s.charAt(j) == s.charAt(i)) {
                j++;
            }
             next[i] = j;
        }
        return next;
    }
}
